#include <iostream>
#include <vector>
#include <string>

using namespace std;

int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int vis[110][110] = { 0 };

bool flag = false;

bool dfs(vector<string>& board, string word, int x, int y, int pos)
{
    if (word.size() - 1 == pos)
    {
        flag = true;
        return true;
    }

    vis[x][y] = 1;
    for (int i = 0; i < 4; i++)
    {
        int x1 = x + dx[i];
        int y1 = y + dy[i];

        if (x1 >= 0 && x1 < board.size() && y1 >= 0 && y1 < board[0].size() && !vis[x1][y1] && word[pos + 1] == board[x1][y1])
        {
            dfs(board, word, x1, y1, pos + 1);
        }
    }
    vis[x][y] = 0;

    return false;
}




int main()
{
    vector<string> board = { "XYZE","SFZS","XDEE" };
    string word = "XYZZED";


    for (int i = 0; i < board.size(); i++)
    {
        for (int j = 0; j < board[i].size(); j++)
        {
            if (board[i][j] == word[0])
            {
                bool flag1 = dfs(board, word, i, j, 0);
                if (flag)
                {
                    cout << " TRUE " << endl;
                }
            }
        }
    }
    //return false;
    cout << "FALSE !!!" << endl;

	return 0;
}